/**
 * All rights Reserved, Designed By 溪云阁
 * Copyright:    Copyright(C) 2016-2020
 */

package com.algorithm;

import java.util.Arrays;

/**
 * 插入算法
 * @author：溪云阁
 * @date：2020年5月3日
 */

public class InsertAlgorithm {

    /**
     * 插入排序
     * @author 溪云阁
     * @param ins
     * @return int[]
     * 一组无序序列{A1,A2,........An}
     * 先取出A1，然后从A2与A1比较，比较完之后序列状况是{A1,A2}{A3..........An}，这时候其中{A1,A2}就变成有序
     * 然后取出A3 ，放到{A1,A2}有序序列合适位置，从而形成{A1,A2,A3}{A4........An}
     * 重复这个过程，直到取出An放入{A1,A2........An-1}有序序列中
     */
    public static int[] insertSort(int[] ins) {
        for (int i = 1; i < ins.length; i++) {
            // 保存每次需要插入的那个数
            final int temp = ins[i];
            int j;
            for (j = i; j > 0 && ins[j - 1] > temp; j--) {
                // 吧大于需要插入的数往后移动。最后不大于temp的数就空出来j
                ins[j] = ins[j - 1];
            }
            // 将需要插入的数放入这个位置
            ins[j] = temp;
        }
        return ins;
    }

    public static void main(String[] args) {
        final int[] arr = { 7, 8, 12, 4, 16, 12, 10 };
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        insertSort(arr);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }
}
